#ifndef __CE_RBTREE_H__
#define __CE_RBTREE_H__

#include "ce_core.h"

#define RED     0
#define BLK     1

typedef uint64_t    ce_rbtree_key_t;

typedef struct ce_rbtree_node_s ce_rbtree_node_t;

struct ce_rbtree_node_s {
    ce_rbtree_key_t     k;  // key
    ce_rbtree_node_t   *p;  // parent
    ce_rbtree_node_t   *l;  // left
    ce_rbtree_node_t   *r;  // right

    ce_rbtree_node_t   *prev;
    ce_rbtree_node_t   *next;

    unsigned            c:1;  // color
};

typedef struct {
    ce_rbtree_node_t   *root;
    ce_rbtree_node_t   *min;
    ce_rbtree_node_t   *max;
    uint32_t            size;

    unsigned            replace:1;
} ce_rbtree_t;

#define ce_rbtree_init(rbt)                     \
    (rbt)->root = NULL;                         \
    (rbt)->min = NULL;                          \
    (rbt)->max = NULL;                          \
    (rbt)->size = 0;                            \
    (rbt)->replace = 1;

#define ce_rbtree_init_noreplace(rbt)           \
    (rbt)->root = NULL;                         \
    (rbt)->min = NULL;                          \
    (rbt)->max = NULL;                          \
    (rbt)->size = 0;                            \
    (rbt)->replace = 0;

#define ce_rbtree_empty(rbt)                    \
    ((rbt)->root == NULL)

#define ce_rbtree_size(rbt)                     \
    (rbt)->size

#define ce_rbtree_min(rbt)                      \
    (rbt)->min

#define ce_rbtree_max(rbt)                      \
    (rbt)->max

ce_rbtree_node_t *ce_rbtree_prev(ce_rbtree_node_t *n);

ce_rbtree_node_t *ce_rbtree_next(ce_rbtree_node_t *n);

ce_rbtree_node_t *ce_rbtree_get(ce_rbtree_t *rbt, ce_rbtree_key_t key);

void ce_rbtree_insert(ce_rbtree_t *rbt, ce_rbtree_node_t *n);

void ce_rbtree_delete(ce_rbtree_t *rbt, ce_rbtree_key_t key);

void ce_rbtree_delete_by_node(ce_rbtree_t *rbt, ce_rbtree_node_t *n);

#endif
